package DynamicProgramingSeries;

public class LongestValidParenthesesSolution_32 {
    public int longestValidParentheses(String s) {
        int result = 0;
        int[] dp = new int[s.length()];

        for (int i = 1; i < s.length(); i++) {
            // 情况1： s[i]=‘)’ 且 s[i−1]=‘(’，也就是字符串形如'...()'
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    if (i >= 2) {
                        dp[i] = dp[i - 2] + 2; //'...()'
                    } else {
                        dp[i] = 2; //'()'
                    }
                }
                // 情况2： s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”
                // s[i]=')'必须有一个s[i-dp[i-1]-1]='('与之对应
                else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    // 如果i - dp[i - 1]) >= 2，说明之前还可能有满足条件的括号序列'...()((....))'
                    // 我们也会把有效子串之前的有效子串的长度也加上，也就是再加上 dp[i−dp[i−1]−2]
                    if ((i - dp[i - 1]) >= 2) {
                        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;// '....()((...))'
                    } else {
                        dp[i] = dp[i - 1] + 2; // '....)(((...))'
                    }
                }
                result = Math.max(result, dp[i]);
            }
        }
        return result;
    }
}
